JYT's First Post

2022-07-12

1 简介

这是JYT的第一篇hexo博客，主要目的是熟悉markdown语言的语法以及hexo博客的发布。主要内容是分享leetcode上一道执行时间0ms的c++程序题解。

2 问题与题解

2.1 问题描述

给你一个字符串 s，找到 s 中最长的回文子串。

示例1

1
2
输入：s = "babad"
输出："bab"

示例2

1
2
输入：s = "cbbd"
输出："bb"

2.2 算法思想

  • 1 动态规划算法

若字符串的某一子串是回文的，那么当其去掉首尾两字符后所得的新字串仍是回文的。该算法逻辑较为复杂，本题采用中心扩展算法。

  • 2 中心扩展算法

先从较短的回文子串开始，例如”babad”的”a”或者”cbbd”的”bb”，标记该子串的首尾位置并分别向前后进行遍历，若首位置前一字符与尾位置后一字符相等，则移动首尾位置，直至出现不等。较短子串可能为单字符或者连续多字符，需分别讨论。遍历时需注意边界情况，即首尾位置不能超出字符串的范围。最后计算子串长度，并与最长子串长度进行比较。返回时，使用c++字符串分割函数substr()，参数为最长子串的首位置与最长子串长度。

  • 3 特殊讨论

当字符串长度很短（1或2）时可以直接解决。当字符串长度大于2时，为使较短回文子串至少可以向两侧遍历一次，循环中设置子串首位置需从1开始。因此，当字符串由连续多个相同字符组成时，如”ccc”，若不对下标为0的位置进行特殊讨论，会得到错误结果。特别地，若无法找到长度大于1的回文子串，返回第一个字符（字符串格式）即可。

2.3 具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
class Solution {
public:
    string longestPalindrome(string s) {
        //字符串长度为1
        if(s.length() == 1){
            return s;
        }else{
            //字符串长度为2
            if(s.length() == 2){
                if(s[0] == s[1]){
                    return s;
                }else{
                    return s.substr(0,1);
                }
            }else{
                //字符串长度大于2
                int begin = 0;
                int end = 0;
                int left = 0;
                int right = 0;
                int maxi = 1;
                //对下标为0的位置特殊处理
                for(int i = 1; ; i++){
                    if(i == s.length()){
                        return s;
                    }
                    if(s[i] != s[0]){
                        break;
                    }else{
                        maxi++;
                    }
                }
                for(int i = 1; i < s.length() - 1; i++){
                    //较短回文子串长度为1
                    if(s[i+1] != s[i]){
                        left = i;
                        right = i;
                        //若前后字符存在
                        while(left > 0 && right < s.length() - 1){
                            //前后字符相等，移动首尾位置
                            if(s[left-1] == s[right+1]){
                                left = left - 1;
                                right = right + 1;
                            }else{
                                break;//前后字符不等，退出循环
                            }
                        }
                        //所得回文子串长度较大，修改最大结果
                        if(right - left + 1 > maxi){
                            begin = left;
                            end = right;
                            maxi = right - left + 1;
                        }
                    }else{
                        //较短回文子串长度为多个连续相等字符
                        left = i;
                        right = i + 1;
                        while(right < s.length() - 1 && s[right+1] == s[right]){
                            right++;//字符相等，尾位置继续移动
                        }
                        //若前后字符存在
                        while(left > 0 && right < s.length() - 1){
                            //前后字符相等，移动首尾位置
                            if(s[left-1] == s[right+1]){
                                left--;
                                right++;
                            }else{
                                break;//前后字符不等，退出循环
                            }
                        }
                        //所得回文子串长度较大，修改最大结果
                        if(right - left + 1 > maxi){
                            begin = left;
                            end = right;
                            maxi = right - left + 1;
                        }
                    }
                }
                //若最长子串长度为1，返回首字符（字符串格式）
                if(maxi == 1){
                    return s.substr(0,1);
                }else{
                    return s.substr(begin, maxi);//返回最长子串
                }
            }
        }
    }
};

2.4 不足与收获

  • 代码分类讨论较多，经一定改进可以减少讨论，使代码更简洁。

  • 目前只有c++代码，日后有空可以补写python代码。

  • leetcode的输入输出与通常程序区别较大，本次进一步加深对leetcode输入输出的理解。

3 今后安排

  • 使用markdown写一份leetcode题解的工作量不低于写一道新题，时间原因不可能每道题都发布题解。争取每日一题，每周2-3份题解吧。

  • 最近开始学习b站古月居的ROS入门，根据学习情况随缘笔记吧。